package tree.递归;

import po.TreeNode;

import java.util.*;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N二叉树的垂序遍历987.java
 * @Description https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/
 * @createTime 2021年08月17日 20:46:00
 */
public class N二叉树的垂序遍历987 {
	Map<TreeNode, int[]> map = new HashMap<>(); // col, row, val

	public List<List<Integer>> verticalTraversal(TreeNode root) {
		//map  key为节点  value为 节点和对应节点的列，行和值的数组
		map.put(root, new int[] {0, 0, root.val});
		//dfs迭代节点
		dfs(root);
		List<int[]> list = new ArrayList<>(map.values());

		Collections.sort(list, (a, b) -> {
			//先按照列排序，小的在前面
			if (a[0] != b[0]) { return a[0] - b[0]; }
			//按照行排序，小的在前面
			if (a[1] != b[1]) { return a[1] - b[1]; }
			//按照值排序，小的在前面
			return a[2] - b[2];
		});
		int n = list.size();
		List<List<Integer>> ans = new ArrayList<>();
		for (int i = 0; i < n; ) {
			int j = i;
			List<Integer> tmp = new ArrayList<>();
			//迭代这个排序号的数组集合，列值相等的保存到一个结果集合中
			while (j < n && list.get(j)[0] == list.get(i)[0]) {
				//添加对应的节点值到集合中
				tmp.add(list.get(j++)[2]);
			}
			ans.add(tmp);
			i = j;
		}
		return ans;
	}

	void dfs(TreeNode root) {
		if (root == null) { return; }
		int[] info = map.get(root);
		int col = info[0], row = info[1], val = info[2];
		if (root.left != null) {
			map.put(root.left, new int[] {col - 1, row + 1, root.left.val});
			dfs(root.left);
		}
		if (root.right != null) {
			map.put(root.right, new int[] {col + 1, row + 1, root.right.val});
			dfs(root.right);
		}
	}
}
